Search Results

Documents authored by Ó Catháin, Padraig


Document
Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

Authors: Matti Karppa, Petteri Kaski, Jukka Kohonen, and Padraig Ó Catháin

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
We derandomize G. Valiant's [J.ACM 62(2015) Art.13] subquadratic-time algorithm for finding outlier correlations in binary data. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant's randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Our main technical tool for derandomization is an explicit family of correlation amplifiers built via a family of zigzag-product expanders in Reingold, Vadhan, and Wigderson [Ann. of Math 155(2002), 157-187]. We say that a function f:{-1,1}^d ->{-1,1}^D is a correlation amplifier with threshold 0 <= tau <= 1, error gamma >= 1, and strength p an even positive integer if for all pairs of vectors x,y in {-1,1}^d it holds that (i) |<x,y>|<tau d implies |<f(x),f(y)>| <= (tau*gamma)^p*D; and (ii) |<x,y>| >= tau*d implies (<x,y>/gamma^d})^p*D <= <f(x),f(y)> <= (gamma*<x,y>/d)^p*D.

Cite as

Matti Karppa, Petteri Kaski, Jukka Kohonen, and Padraig Ó Catháin. Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{karppa_et_al:LIPIcs.ESA.2016.52,
  author =	{Karppa, Matti and Kaski, Petteri and Kohonen, Jukka and \'{O} Cath\'{a}in, Padraig},
  title =	{{Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.52},
  URN =		{urn:nbn:de:0030-drops-63944},
  doi =		{10.4230/LIPIcs.ESA.2016.52},
  annote =	{Keywords: correlation, derandomization, outlier, similarity search, expander graph}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail